#ifndef cathlibcpp_iterator_H
#define cathlibcpp_iterator_H

// File:       iterator.h
// Author:     (c) Miles Sabin, 1996
// Purpose:    approximation to ANSI C++ iterator templates


#ifndef included_stddef_H
#define included_stddef_H
#include <stddef.h>            // for ptrdiff_t
#endif

#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_iosfwd_H
#include "iosfwd.h"
#endif


#ifdef PROBLEM_LONG_NAMES

// abbreviations to stop CFront choking on long names

#define input_iterator                      __ii
#define input_iterator_tag                  __iit
#define input_iterator_tag_                 __iit_

#define output_iterator                     __oi
#define output_iterator_tag                 __oit
#define output_iterator_tag_                __oit_

#define forward_iterator                    __fi
#define forward_iterator_tag                __fit
#define forward_iterator_tag_               __fit_

#define bidirectional_iterator              __bi
#define bidirectional_iterator_tag          __bit
#define bidirectional_iterator_tag_         __bit_

#define random_access_iterator              __rai
#define random_access_iterator_tag          __rait
#define random_access_iterator_tag_         __rait_

#define reverse_iterator                    __ri
#define reverse_bidirectional_iterator      __rbi

#define front_insert_iterator               __fii
#define back_insert_iterator                __bii
#define insert_iterator                     __insi

#endif


// iterator tags typedef'd to opaque pointers because CFront won't instantiate empty structs

typedef struct input_iterator_tag_*         input_iterator_tag;
typedef struct output_iterator_tag_*        output_iterator_tag;
typedef struct forward_iterator_tag_*       forward_iterator_tag;
typedef struct bidirectional_iterator_tag_* bidirectional_iterator_tag;
typedef struct random_access_iterator_tag_* random_access_iterator_tag;


// iterator categories

template<class T>
struct input_iterator {};

struct output_iterator {};

template<class T>
struct forward_iterator {};

template<class T>
struct bidirectional_iterator {};

template<class T>
struct random_access_iterator {};


// iterator category selectors

template<class T>
inline input_iterator_tag iterator_category(input_iterator<T> const&);

inline output_iterator_tag iterator_category(output_iterator const&);

template<class T>
inline forward_iterator_tag iterator_category(forward_iterator<T> const&);

template<class T>
inline bidirectional_iterator_tag iterator_category(bidirectional_iterator<T> const&);

template<class T>
inline random_access_iterator_tag iterator_category(random_access_iterator<T> const&);

template<class T>
inline random_access_iterator_tag iterator_category(T const*);


// iterator value type selectors

template<class T>
inline T* value_type(input_iterator<T> const&);

template<class T>
inline T* value_type(forward_iterator<T> const&);

template<class T>
inline T* value_type(bidirectional_iterator<T> const&);

template<class T>
inline T* value_type(random_access_iterator<T> const&);

template<class T>
inline T* value_type(T const*);


// iterator distance type selectors ... only ptrdiff_t supported

template<class T>
inline ptrdiff_t* distance_type(input_iterator<T> const&);

template<class T>
inline ptrdiff_t* distance_type(forward_iterator<T> const&);

template<class T>
inline ptrdiff_t* distance_type(bidirectional_iterator<T> const&);

template<class T>
inline ptrdiff_t* distance_type(random_access_iterator<T> const&);

template<class T>
inline ptrdiff_t* distance_type(T const*);


// iterator operations

template<class InputIterator>
inline void advance(InputIterator& i, ptrdiff_t n)

template<class InputIterator>
inline void distance(InputIterator first, InputIterator last, ptrdiff_t& n)


// reverse iterator adapters

template<class BidirectionalIterator, class T, class Reference>
class reverse_bidirectional_iterator : public bidirectional_iterator<T>
{
# define this_type reverse_bidirectional_iterator<BidirectionalIterator, T, Reference>

  public:

    // constructors
    reverse_bidirectional_iterator()
      {}

    reverse_bidirectional_iterator(BidirectionalIterator const& x)
      : current(x)
      {}

    // accessors
    Reference operator*() const
      { BidirectionalIterator tmp = current; return *--tmp; }

#ifndef PROBLEM_MEMBER_ACCESS
    T* operator->() const
      { BidirectionalIterator tmp = current; return &*--tmp; }
#endif

    // mutators
    this_type& operator++()
      { --current; return *this; }

    this_type operator++(int)
      { return this_type(current--); }

    this_type& operator--()
      { ++current; return *this; }

    this_type operator--(int)
      { return this_type(current++); }

    // explicit conversions
    BidirectionalIterator base() const
      { return current; }

  protected:

    BidirectionalIterator current;

# undef this_type
};


template<class BidirectionalIterator, class T, class Reference>
inline bool operator==(reverse_bidirectional_iterator<BidirectionalIterator, T, Reference> const& x,
                       reverse_bidirectional_iterator<BidirectionalIterator, T, Reference> const& y);


template<class RandomAccessIterator, class T, class Reference>
class reverse_iterator : public random_access_iterator<T>
{
# define this_type reverse_iterator<RandomAccessIterator, T, Reference>

  public:

    // constructors
    reverse_iterator()
      {}

    reverse_iterator(RandomAccessIterator const& x)
      : current(x)
      {}

    // accessors
    Reference operator*() const
      { return *(current-1); }

#ifndef PROBLEM_MEMBER_ACCESS
    Reference* operator->() const
      { return &(*current-1); }
#endif

    this_type operator+(ptrdiff_t n) const
      { return this_type(current-n); }

    this_type operator-(ptrdiff_t n) const
      {  return this_type(current+n); }

    Reference operator[](ptrdiff_t n) const
      { return current[-n-1]; }

    // mutators
    this_type& operator++()
      { --current; return *this; }

    this_type operator++(int)
      { return this_type(current--); }

    this_type& operator--()
      { ++current; return *this; }

    this_type operator--(int)
      { return this_type(current++); }

    this_type& operator+=(ptrdiff_t n)
      { current -= n; return *this; }

    this_type& operator-=(ptrdiff_t n)
      { current += n; return *this; }

    // explicit conversions
    RandomAccessIterator base() const
      { return current; }

  protected:

    RandomAccessIterator current;

# undef this_type
};


template<class RandomAccessIterator, class T, class Reference>
inline bool operator==(reverse_iterator<RandomAccessIterator, T, Reference> const& x,
                       reverse_iterator<RandomAccessIterator, T, Reference> const& y);

template<class RandomAccessIterator, class T, class Reference>
inline bool operator<(reverse_iterator<RandomAccessIterator, T, Reference> const& x,
                      reverse_iterator<RandomAccessIterator, T, Reference> const& y);

template<class RandomAccessIterator, class T, class Reference>
inline ptrdiff_t operator-(reverse_iterator<RandomAccessIterator, T, Reference> const& x,
                           reverse_iterator<RandomAccessIterator, T, Reference> const& y);

template<class RandomAccessIterator, class T, class Reference>
inline reverse_iterator<RandomAccessIterator, T, Reference>
  operator+(ptrdiff_t n, reverse_iterator<RandomAccessIterator, T, Reference> const& x);


// insert iterator adapters

template<class Container, class value_type>
class back_insert_iterator : public output_iterator
{
  public:

    // constructors
    back_insert_iterator(Container& x)
      : container(x)
      {}

    // mutators
    back_insert_iterator<Container, value_type>& operator=(value_type const& value)
      { container.push_back(value); return *this; }

    back_insert_iterator<Container, value_type>& operator*()
      { return *this; }

    back_insert_iterator<Container, value_type>& operator++()
      { return *this; }

    back_insert_iterator<Container, value_type>& operator++(int)
      { return *this; }

  protected:

    Container& container;
};

template<class Container, class value_type>
inline back_insert_iterator<Container, value_type> back_inserter(Container& x, value_type const*);


template<class Container, class value_type>
class front_insert_iterator : public output_iterator
{
  public:

    // constructors
    front_insert_iterator(Container& x)
      : container(x)
      {}

    // mutators
    front_insert_iterator<Container, value_type>& operator=(value_type const& value)
      {
        container.push_front(value);
        return *this;
      }

    front_insert_iterator<Container, value_type>& operator*()
      { return *this; }

    front_insert_iterator<Container, value_type>& operator++()
      { return *this; }

    front_insert_iterator<Container, value_type>& operator++(int)
      { return *this; }

  protected:

    Container& container;
};

template<class Container, class value_type>
inline front_insert_iterator<Container, value_type> front_inserter(Container& x, value_type const*);


template<class Container, class iterator, class value_type>
class insert_iterator : public output_iterator
{
  public:

    // constructors
    insert_iterator(Container& x, iterator const& i)
      : container(x),
        iter(i)
      {}

    // mutators
    insert_iterator<Container, iterator, value_type>& operator=(value_type const& value)
      {
        iter = container.insert(iter, value);
        ++iter;
        return *this;
      }

    insert_iterator<Container, iterator, value_type>& operator*()
      { return *this; }

    insert_iterator<Container, iterator, value_type>& operator++()
      { return *this; }

    insert_iterator<Container, iterator, value_type>& operator++(int)
      { return *this; }

  protected:

    Container& container;
    iterator iter;
};

template<class Container, class Iterator, class value_type>
inline insert_iterator<Container, Iterator, value_type> inserter(Container& x, Iterator const& i, value_type const*);


// stream iterators

template<class T>
class istream_iterator : public input_iterator<T>
{
  friend bool operator==(istream_iterator<T> const& lhs, istream_iterator<T> const& rhs);

  public:

    // constructors
    istream_iterator()
      : stream_(0)
      {}

    istream_iterator(istream& s)
      : stream_(&s)
      { get_next_value(); }

    istream_iterator(istream_iterator<T> const& rhs)
      : stream_(rhs.stream_),
        value_(rhs.value_)
      {}

    ~istream_iterator()
      {}

    // accessors
    T const& operator*() const
      { return value_; }

    // mutators
    istream_iterator<T>& operator++()
      {
        get_next_value();
        return *this;
      }

    istream_iterator<T> operator++(int)
      {
        istream_iterator<T> tmp = *this;
        get_next_value();
        return tmp;
      }

  private:

    void get_next_value()
    {
      if(stream_ != 0)
      {
        (*stream_) >> value_;
        if(!(*stream_))
          stream_ = 0;
      }
    }

    istream* stream_;
    T value_;
};

template<class T>
inline bool operator==(istream_iterator<T> const& lhs, istream_iterator<T> const& rhs)
  { return lhs.stream_ == rhs.stream_; }


template<class T>
class ostream_iterator : public output_iterator
{
  public:

    // constructors
    ostream_iterator(ostream& s)
      : stream_(s),
        delimiter_(0)
      {}

    ostream_iterator(ostream& s, char const* delimiter)
      : stream_(s),
        delimiter_(delimiter)
      {}

    ostream_iterator(ostream_iterator<T> const& rhs)
      : stream_(rhs.stream_),
        delimiter_(rhs.delimiter_)
      {}

    ~ostream_iterator()
      {}

    // mutators
    ostream_iterator<T>& operator=(T const& value)
      {
        stream_ << value;
        if(delimiter_ != 0)
          stream_ << delimiter_;
        return *this;
      }

    ostream_iterator<T>& operator*()
      { return *this; }

    ostream_iterator<T>& operator++()
      { return *this; }

    ostream_iterator<T>& operator++(int)
      { return *this; }

  private:

    ostream& stream_;
    char const* delimiter_;
};


template<class char_type, class traits>
class istreambuf_iterator;


template<class char_type, class traits>
class istreambuf_iterator_proxy
{
  friend class istreambuf_iterator<char_type, traits>;

  public:

    char_type operator*()
      { return keep_; }

  private:

    proxy(char_type c, basic_streambuf_char* sbuf)
      : keep_(c),
        sbuf_(sbuf)
      {}

    char_type keep_;
    basic_streambuf_char* sbuf_;
};


template<class char_type, class traits>
class istreambuf_iterator : public input_iterator<char_type>
{
  public:

    istreambuf_iterator()
      : sbuf_(0)
      {}

    istreambuf_iterator(istream& s)
      : sbuf_(s.rdbuf())
      {}

    istreambuf_iterator(streambuf* s)
      : sbuf_(s)
      {}

    istreambuf_iterator(istreambuf_iterator_proxy<char_type, traits> const& p)
      : sbuf_(p.sbuf_)
      {}

    char_type operator*() const
      { return sbuf_->sgetc(); }

    istreambuf_iterator<char_type, traits>& operator++()
      {
        if(sbuf_->sbumpc() == traits::eof())
          sbuf_ = 0;
        return *this;
      }

    istreambuf_iterator_proxy<char_type, traits> operator++(int)
      { return istreambuf_iterator_proxy<char_type, traits>(sbuf_->sbumpc(), sbuf_); }

    bool equal(istreambuf_iterator<char_type, traits> const& b) const
      { return (sbuf_ == 0 && b.sbuf_ == 0) || (sbuf_ != 0 && b.sbuf_ != 0); }

  private:

    streambuf* sbuf_;
};

template<class char_type, class traits>
inline bool operator==(istreambuf_iterator<char_type, traits> const& lhs, istreambuf_iterator<char_type, traits> const& rhs)
{
  return lhs.equal(rhs);
}


template<class char_type, class traits>
class ostreambuf_iterator : public output_iterator
{
  public:

    ostreambuf_iterator(ostream& s)
      : sbuf_(s.rdbuf())
      {}

    ostreambuf_iterator(streambuf* s)
      : sbuf_(s)
      {}

    ostreambuf_iterator<char_type, traits>& operator=(char_type c)
      {
        if(sbuf_ != 0 && sbuf_->sputc(c) == traits::eof())
          sbuf_ = 0;
        return *this;
      }

    ostreambuf_iterator<char_type, traits>& operator*()
      { return *this; }

    ostreambuf_iterator<char_type, traits>& operator++()
      { return *this; }

    ostreambuf_iterator<char_type, traits>& operator++(int)
      { return *this; }

    bool failed() const
      { return sbuf_ == 0; }

  private:

    streambuf* sbuf_;
};


// Implementation of iterator category selectors

template<class T>
inline input_iterator_tag iterator_category(input_iterator<T> const&)
{
  return (input_iterator_tag)0;
}

inline output_iterator_tag iterator_category(output_iterator const&)
{
  return (output_iterator_tag)0;
}

template<class T>
inline forward_iterator_tag iterator_category(forward_iterator<T> const&)
{
  return (forward_iterator_tag)0;
}

template<class T>
inline bidirectional_iterator_tag iterator_category(bidirectional_iterator<T> const&)
{
  return (bidirectional_iterator_tag)0;
}

template<class T>
inline random_access_iterator_tag iterator_category(random_access_iterator<T> const&)
{
  return (random_access_iterator_tag)0;
}

template<class T>
inline random_access_iterator_tag iterator_category(T const*)
{
  return (random_access_iterator_tag)0;
}


// Implementation of iterator value type selectors

template<class T>
inline T* value_type(input_iterator<T> const&)
{
  return (T*)(0);
}

template<class T>
inline T* value_type(forward_iterator<T> const&)
{
  return (T*)(0);
}

template<class T>
inline T* value_type(bidirectional_iterator<T> const&)
{
  return (T*)(0);
}

template<class T>
inline T* value_type(random_access_iterator<T> const&)
{
  return (T*)(0);
}

template<class T>
inline T* value_type(T const*)
{
  return (T*)(0);
}


// Implementation of iterator distance type selectors ... only ptrdiff_t supported

template<class T>
inline ptrdiff_t* distance_type(input_iterator<T> const&)
{
  return (ptrdiff_t*)(0);
}

template<class T>
inline ptrdiff_t* distance_type(forward_iterator<T> const&)
{
  return (ptrdiff_t*)(0);
}

template<class T>
inline ptrdiff_t* distance_type(bidirectional_iterator<T> const&)
{
  return (ptrdiff_t*)(0);
}

template<class T>
inline ptrdiff_t* distance_type(random_access_iterator<T> const&)
{
  return (ptrdiff_t*)(0);
}

template<class T>
inline ptrdiff_t* distance_type(T const*)
{
  return (ptrdiff_t*)(0);
}


// Implementation of iterator advance operation

template<class InputIterator>
inline void tagged_advance(InputIterator& i, ptrdiff_t n, input_iterator_tag)
{
  while(n--)
    ++i;
}

template<class ForwardIterator>
inline void tagged_advance(ForwardIterator& i, ptrdiff_t n, forward_iterator_tag)
{
  while(n--)
    ++i;
}

template<class BidirectionalIterator>
inline void tagged_advance(BidirectionalIterator& i, ptrdiff_t n, bidirectional_iterator_tag)
{
  if(n >= 0)
    while(n--)
      ++i;
  else
    while(n++)
      --i;
}

template<class RandomAccessIterator>
inline void tagged_advance(RandomAccessIterator& i, ptrdiff_t n, random_access_iterator_tag)
{
  i += n;
}

template<class InputIterator>
inline void advance(InputIterator& i, ptrdiff_t n)
{
  tagged_advance(i, n, iterator_category(i));
}


// Implementation of iterator distance operation

template<class InputIterator>
inline void tagged_distance(InputIterator const& first, InputIterator const& last, ptrdiff_t& n, input_iterator_tag)
{
  // weird CFront bug
  InputIterator first_ = first;

  while(first_ != last)
  {
    ++first_;
    ++n;
  }
}

template<class ForwardIterator>
inline void tagged_distance(ForwardIterator const& first, ForwardIterator const& last, ptrdiff_t& n, forward_iterator_tag)
{
  // weird CFront bug
  ForwardIterator first_ = first;

  while(first_ != last)
  {
    ++first_;
    ++n;
  }
}

template<class BidirectionalIterator>
inline void tagged_distance(BidirectionalIterator const& first, BidirectionalIterator const& last, ptrdiff_t& n, bidirectional_iterator_tag)
{
  // weird CFront bug
  BidirectionalIterator first_ = first;

  while(first_ != last)
  {
    ++first_;
    ++n;
  }
}

template<class RandomAccessIterator>
inline void tagged_distance(RandomAccessIterator first, RandomAccessIterator last, ptrdiff_t& n, random_access_iterator_tag)
{
  n += last-first;
}

template<class InputIterator>
inline void distance(InputIterator first, InputIterator last, ptrdiff_t& n)
{
  tagged_distance(first, last, n, iterator_category(first));
}


// Implementation of reverse_bidirectional_iterator<T> free fns

template<class BidirectionalIterator, class T, class Reference>
inline bool operator==(reverse_bidirectional_iterator<BidirectionalIterator, T, Reference> const& x,
                       reverse_bidirectional_iterator<BidirectionalIterator, T, Reference> const& y)
{
  return x.base() == y.base();
}


// implementation of reverse_iterator<T> free fns

template<class RandomAccessIterator, class T, class Reference>
inline bool operator==(reverse_iterator<RandomAccessIterator, T, Reference> const& x,
                       reverse_iterator<RandomAccessIterator, T, Reference> const& y)
{
  return x.base() == y.base();
}

template<class RandomAccessIterator, class T, class Reference>
inline bool operator<(reverse_iterator<RandomAccessIterator, T, Reference> const& x,
                      reverse_iterator<RandomAccessIterator, T, Reference> const& y)
{
  return y.base() < x.base();
}

template<class RandomAccessIterator, class T, class Reference>
inline ptrdiff_t operator-(reverse_iterator<RandomAccessIterator, T, Reference> const& x,
                           reverse_iterator<RandomAccessIterator, T, Reference> const& y)
{
  return y.base()-x.base();
}

template<class RandomAccessIterator, class T, class Reference>
inline reverse_iterator<RandomAccessIterator, T, Reference>
  operator+(ptrdiff_t n, reverse_iterator<RandomAccessIterator, T, Reference> const& x)
{
  return reverse_iterator<RandomAccessIterator, T, Reference>(x.current-n);
}


// Implementation of back_insert_iterator<Container, value_type> free fns

template<class Container, class value_type>
inline back_insert_iterator<Container, value_type> back_inserter(Container& x, value_type const*)
{
  return back_insert_iterator<Container, value_type>(x);
}


// Implementation of front_insert_iterator<Container, value_type> free fns

template<class Container, class value_type>
inline front_insert_iterator<Container, value_type> front_inserter(Container& x, value_type const*)
{
  return front_insert_iterator<Container, value_type>(x);
}


// Implementation of insert_iterator<Container, value_type> free fns

template<class Container, class Iterator, class value_type>
inline insert_iterator<Container, Iterator, value_type> inserter(Container& x, Iterator const& i, value_type const*)
{
  return insert_iterator<Container, Iterator, value_type>(x, i);
}

#endif
